package tree;

public class BackOrderArray {
	//check if an array could be a back order travesal of a BST
	public static boolean isBack(int[] array, int start, int end){
		int root = array[end];
		int i = end - 1;
		
		while(array[i] > root && i >= start){
			i--;
		}
		//now i is the greatest element in the right subtree
		//all the element between start and i is the left subtree
		for(int j = start; j <= i; j++){
			if(array[i] > root)
				return false;
		}
		
		
		
		boolean left = true;
		if(i > start)
			left = isBack(array, start, i);
		
		boolean right = true;
		if(i < end -1)
			right = isBack(array, i + 1, end);
		
		return (left && right);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
